#pragma once

#include <cstddef>
// iterator type tag -> class type tag
// just for show, not used in this code, use std::iterrator_tag instead
struct input_iterator_tag
{
};
struct output_iterator_tag
{
};
struct forward_iterator_tag : public input_iterator_tag
{
};
struct bidirectional_iterator_tag : public forward_iterator_tag
{
};
struct random_access_iterator_tag : public bidirectional_iterator_tag
{
};

// for iterator type traits
template <typename T>
struct hamster_iterator_traits
{
    using value_type = typename T::value_type;
    using pointer = typename T::pointer;
    using reference = typename T::reference;
    // class type iterator
    using difference_type = typename T::difference_type;
    using iterator_category = typename T::iterator_category;
};

// partial specialization for pointer type
template <typename T>
struct hamster_iterator_traits<T *>
{
    using value_type = T;
    using pointer = T *;
    using reference = T &;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::random_access_iterator_tag;
};

// partial specialization for const pointer type
template <typename T>
struct hamster_iterator_traits<const T *>
{
    using value_type = T;
    using pointer = const T *;
    using reference = const T &;
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::random_access_iterator_tag;
};

template <class _Tp, class _Distance> 
struct input_iterator 
{
  typedef input_iterator_tag iterator_category;
  typedef _Tp                value_type;
  typedef _Distance          difference_type;
  typedef _Tp*               pointer;
  typedef _Tp&               reference;
};

struct output_iterator 
{
  typedef output_iterator_tag iterator_category;
  typedef void                value_type;
  typedef void                difference_type;
  typedef void                pointer;
  typedef void                reference;
};

template <class _Tp, class _Distance> 
struct forward_iterator 
{
  typedef forward_iterator_tag iterator_category;
  typedef _Tp                  value_type;
  typedef _Distance            difference_type;
  typedef _Tp*                 pointer;
  typedef _Tp&                 reference;
};

template <class _Tp, class _Distance> 
struct bidirectional_iterator 
{
  typedef bidirectional_iterator_tag iterator_category;
  typedef _Tp                        value_type;
  typedef _Distance                  difference_type;
  typedef _Tp*                       pointer;
  typedef _Tp&                       reference;
};

template <class _Tp, class _Distance> 
struct random_access_iterator 
{
  typedef random_access_iterator_tag iterator_category;
  typedef _Tp                        value_type;
  typedef _Distance                  difference_type;
  typedef _Tp*                       pointer;
  typedef _Tp&                       reference;
};

// reverse_bidirectional_iterator
template <
    typename _BidirectionalIterator,
    typename _Value_type,
    typename _Reference = _Value_type &,
    typename _Distance = std::ptrdiff_t>
class reverse_bidirectional_iterator
{
    using _Self = reverse_bidirectional_iterator<
        _BidirectionalIterator,
        _Value_type,
        _Reference,
        _Distance>;

protected:
    _BidirectionalIterator current;

public:
    using iterator_category = bidirectional_iterator_tag;
    using value_type = _Value_type;
    using difference_type = _Distance;
    using pointer = _Value_type *;
    using reference = _Reference;

    reverse_bidirectional_iterator() {}

    explicit reverse_bidirectional_iterator(_BidirectionalIterator _x) : current(_x) {}

    _BidirectionalIterator base() { return current; }

    // 指向“当前反向迭代器位置的下一个元素”的迭代器
    _Reference operator*() const
    {
        _BidirectionalIterator _temp = current;
        return *--_temp;
    }

    pointer operator->() const
    {
        return &(operator*());
    }

    _Self operator++(int)
    {
        _Self _temp = *this;
        ++current;
        return _temp;
    }

    _Self operator++()
    {
        --current;
        return current;
    }

    _Self operator--()
    {
        ++current;
        return current;
    }

    _Self operator--(int)
    {
        _Self _temp = current;
        ++current;
        return _temp;
    }
};

template <class _InputIterator, class _Distance>
inline void __distance(_InputIterator __first, _InputIterator __last,
                       _Distance &__n, input_iterator_tag)
{
    while (__first != __last)
    {
        ++__first;
        ++__n;
    }
}

template <class _RandomAccessIterator, class _Distance>
inline void __distance(_RandomAccessIterator __first,
                       _RandomAccessIterator __last,
                       _Distance &__n, random_access_iterator_tag)
{
    __n += __last - __first;
}

template <class _InputIterator, class _Distance>
inline void distance(_InputIterator __first,
                     _InputIterator __last, _Distance &__n)
{
    __distance(__first, __last, __n, iterator_category(__first));
}

template <class _InputIterator>
inline typename hamster_iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
{
  typename hamster_iterator_traits<_InputIterator>::difference_type __n = 0;
  while (__first != __last) {
    ++__first; ++__n;
  }
  return __n;
}

template <class _RandomAccessIterator>
inline typename hamster_iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
           random_access_iterator_tag) {
  return __last - __first;
}

template <class _InputIterator>
inline typename hamster_iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last) {
  typedef typename hamster_iterator_traits<_InputIterator>::iterator_category 
    _Category;
  return __distance(__first, __last, _Category());
}
